package 数据结构专栏.A_二叉树专栏.B_深度问题;


import 数据结构专栏.A_二叉树专栏.TreeNode;

/**
 * @Title
 * @Author zhengqiang.tan
 * @Date 2021/4/17 4:01 PM
 */
public class 树的最大最小深度 {
    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.buildDemoTreeNode();
        System.out.println(treeMaxDepth(treeNode));
        System.out.println(treeMinDepth(treeNode));
    }


    /**
     * 最大深度
     */
    public static int treeMaxDepth(TreeNode curr) {
        if (curr != null) {
            int left = treeMaxDepth(curr.left);
            int right = treeMaxDepth(curr.right);
            return left > right ? left + 1 : right + 1;
        }
        return 0;
    }


    /**
     * 最小深度
     */
    public static int treeMinDepth(TreeNode root) {
        TreeNode curr = root;
        if (curr == null) return 0;
        if (curr.left == null && curr.right == null) return 1;

        int min_depth = Integer.MAX_VALUE;
        if (curr.left != null) {
            min_depth = Math.min(treeMinDepth(curr.left), min_depth);
        }
        if (curr.right != null) {
            min_depth = Math.min(treeMinDepth(curr.right), min_depth);
        }
        return min_depth + 1;
    }
}
